package book;

public class SudokuSolution {
    static final int SIZE = 9;
    int[][] matrix = {
            {6, 5, 0, 8, 7, 3, 0, 9, 0},
            {0, 0, 3, 2, 5, 0, 0, 0, 8},
            {9, 8, 0, 1, 0, 4, 3, 5, 7},
            {1, 0, 5, 0, 0, 0, 0, 0, 0},
            {4, 0, 0, 0, 0, 0, 0, 0, 2},
            {0, 0, 0, 0, 0, 0, 5, 0, 3},
            {5, 7, 8, 3, 0, 1, 0, 2, 6},
            {2, 0, 0, 0, 4, 8, 9, 0, 0},
            {0, 9, 0, 6, 2, 5, 0, 8, 1}
    };

    // 输出结果
    void printSudoku() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) 
                System.out.print(matrix[i][j] + "\t");
            System.out.println();
        }
    }

    // 返回下一个未填的格子
    int[] numberUnassigned(int row, int col) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                // 该单元格未填写
                if (matrix[i][j] == 0) {
                    int[] a = { 1, i, j };
                    return a;
                }
            }
        }
        // 没有未填格子，返回0
        int[] a = { 0, -1, -1 };
        return a;
    }

    // 检查是否能将值n填写在单元格[r][c]处
    boolean isSafe(int n, int r, int c) {
        // 检查所在行有无重复
        for (int i = 0; i < SIZE; i++) {
            if (matrix[r][i] == n)
                return false;
        }
        // 检查所在列有无重复
        for (int i = 0; i < SIZE; i++) {
            if (matrix[i][c] == n)
                return false;
        }
        // 检查所在九宫格
        int row_start = (r / 3) * 3;
        int col_start = (c / 3) * 3;
        for (int i = row_start; i < row_start + 3; i++) {
            for (int j = col_start; j < col_start + 3; j++) {
                if (matrix[i][j] == n)
                    return false;
            }
        }
        // 上述情况都没有，则说明可以填写n
        return true;
    }

    //使用回溯法解决数独问题
    boolean solveSudoku() {
        int row = 0;
        int col = 0;
        int[] a = numberUnassigned(row, col);
        if (a[0] == 0)
            return true;

        // 尝试填写数字1-9到下一个未填写的格子
        row = a[1];
        col = a[2];
        for (int i = 1; i <= SIZE; i++) {
            if (isSafe(i, row, col)) {
                matrix[row][col] = i;
                // 通过递归执行DFS搜索
                if (solveSudoku())
                    return true;
                // 还原状态
                matrix[row][col] = 0;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        SudokuSolution sln = new SudokuSolution();
        if (sln.solveSudoku())
            sln.printSudoku();
        else
            System.out.println("该数独问题无解!");
    }
}
